

import java.util.List;

public class BinaryTreeTest {

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        BinaryTree.TreeNode root = tree.createTree(); // 创建测试树

        // 1. 测试三种遍历方式
        System.out.println("\n=== 遍历测试 ===");
        System.out.print("前序遍历: ");
        tree.preOrder(root); // A B D E H C F G 

        System.out.print("\n中序遍历: ");
        tree.inOrder(root); // D B E H A F C G 

        System.out.print("\n后序遍历: ");
        tree.postOrder(root); // D H E B F G C A 

        // 2. 测试节点数量统计
        System.out.println("\n\n=== 节点统计测试 ===");
        tree.getNodeSize1(root);
        System.out.println("遍历法节点数: " + tree.nodeSize); // 8
        System.out.println("递归法节点数: " + tree.getNodeSize2(root)); // 8

        // 3. 测试叶子节点统计
        tree.getLeafNodeCount1(root);
        System.out.println("\n遍历法叶子节点: " + tree.leafCount); // 4 (D, H, F, G)
        System.out.println("递归法叶子节点: " + tree.getLeafNodeCount2(root)); // 4

        // 4. 测试第K层节点数
        System.out.println("\n=== 层级节点测试 ===");
        System.out.println("第1层节点: " + tree.getKLevelNodeCount(root, 1)); // 1 (A)
        System.out.println("第3层节点: " + tree.getKLevelNodeCount(root, 3)); // 4 (D, E, F, G)
        System.out.println("第4层节点: " + tree.getKLevelNodeCount(root, 4)); // 1 (H)

        // 5. 测试树高度
        System.out.println("\n树高度: " + tree.getHeight1(root)); // 4
        System.out.println("树高度(方法2): " + tree.getHeight2(root)); // 4

        // 6. 测试节点查找
        System.out.println("\n=== 节点查找测试 ===");
        System.out.println("查找'H': " + (tree.find(root, 'H') != null ? "成功" : "失败")); // 成功
        System.out.println("查找'X': " + (tree.find(root, 'X') != null ? "成功" : "失败")); // 失败

        // 7. 测试树相同判断
        System.out.println("\n=== 树比较测试 ===");
        BinaryTree.TreeNode root2 = tree.createTree(); // 创建相同树
        System.out.println("相同树比较: " + tree.isSameTree(root, root2)); // true

        BinaryTree.TreeNode diffRoot = new BinaryTree.TreeNode('A');
        diffRoot.left = new BinaryTree.TreeNode('B');
        System.out.println("不同树比较: " + tree.isSameTree(root, diffRoot)); // false

        // 8. 测试子树判断
        BinaryTree.TreeNode sub = new BinaryTree.TreeNode('B');
        sub.left = new BinaryTree.TreeNode('D');
        sub.right = new BinaryTree.TreeNode('E');
        sub.right.right = new BinaryTree.TreeNode('H');
        System.out.println("\n子树检测: " + tree.isSubtree(root, sub)); // true

        // 9. 测试二叉树翻转
        System.out.println("\n=== 二叉树翻转测试 ===");
        System.out.print("原始树前序: ");
        tree.preOrder(root); // A B D E H C F G 

        BinaryTree.TreeNode inverted = tree.invertTree(root);
        System.out.print("\n翻转树前序: ");
        tree.preOrder(inverted); // A C G F B E H D 

        // 10. 测试平衡二叉树判断
        System.out.println("\n\n平衡检查(方法1): " + tree.isBalanced1(root)); // true
        System.out.println("平衡检查(方法2): " + tree.isBalanced2(root)); // true

        // 11. 测试对称二叉树
        System.out.println("\n对称检查: " + tree.isSymmetric(root)); // false

        // 12. 测试层序遍历
        System.out.println("\n=== 层序遍历测试 ===");
        System.out.print("常规层序: ");
        tree.levelOrder(root); // A C B F G E D H 

        System.out.println("\n分层输出:");
        List<List<Character>> levels = tree.levelOrder2(root);
        for (List<Character> level : levels) {
            System.out.println(level);
            // [A]
            // [C, B]
            // [F, G, E]
            // [D, H]
        }
    }
}